import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;


public class WordNet 
{
	private final Map<String, LinkedList<Integer>>  mNouns;
	private final java.util.Vector<String>          mSynsetByIndex;
	private final SAP                               mSAP;
	
	static private void checkRootDAG(Digraph G) 
	{
		if(new DirectedCycle(G).hasCycle())
			throw new java.lang.IllegalArgumentException("has cycle");
		
		Digraph GR = G.reverse();
		int numRoots = 0;
		for(int i = 0; i < G.V(); i++)
			if(!G.adj(i).iterator().hasNext())
			{
				BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(GR, i);
				int k = 0;
				for(; k < G.V(); k++) if(!bfs.hasPathTo(k)) break;
				
				if(k == G.V())
					numRoots++;
			}

		if(numRoots != 1)
			throw new java.lang.IllegalArgumentException("Number of roots: " + numRoots);
		
	}
	
	public WordNet(String synsetsFile, String hypernymsFile)
	{
		mNouns = new HashMap<String, LinkedList<Integer>>();
		mSynsetByIndex = new java.util.Vector<String>();
		
		In in = new In(synsetsFile);
		
		int maxSynsetId = 0;
		while(in.hasNextLine())
		{
			String[] tokens = in.readLine().split(",");
			
			final int id         = Integer.parseInt(tokens[0]);
			final String synset  = tokens[1];
			final String[] nouns = synset.split(" ");
			
			for(String noun: nouns)
			{
				LinkedList<Integer> ids = mNouns.get(noun);
				if(ids == null)
				{
					ids = new LinkedList<Integer>();
					mNouns.put(noun, ids);
				}
				
				ids.add(id);
			}
			
			mSynsetByIndex.add(synset);
			
			maxSynsetId = Math.max(maxSynsetId, id);
		}
		in.close();
		
		Digraph G = new Digraph(maxSynsetId + 1);
		
		in = new In(hypernymsFile);
		while(in.hasNextLine())
		{
			String[] tokens = in.readLine().split(",");
			
			int id = Integer.parseInt(tokens[0]);
			for(int i = 1; i < tokens.length; i++)
				G.addEdge(id, Integer.parseInt(tokens[i]));
		}
		in.close();

		checkRootDAG(G);
		
		mSAP = new SAP(G);
	}

	// returns all WordNet nouns
	public Iterable<String> nouns()
	{
		return mNouns.keySet();
	}

	// is the word a WordNet noun?
	public boolean isNoun(String word)
	{
		return mNouns.containsKey(word);
	}

	// distance between nounA and nounB (defined below)
	public int distance(String nounA, String nounB)
	{
		Iterable<Integer> iA = mNouns.get(nounA);
		Iterable<Integer> iB = mNouns.get(nounB);
		
		if(iA == null || iB == null)
			throw new java.lang.IllegalArgumentException();
		
		return mSAP.length(iA, iB);
	}
	
	// a synset (second field of synsets.txt) that is the common ancestor of nounA and nounB
	// in a shortest ancestral path (defined below)
	public String sap(String nounA, String nounB)
	{
		Iterable<Integer> iA = mNouns.get(nounA);
		Iterable<Integer> iB = mNouns.get(nounB);
		
		if(iA == null || iB == null)
			throw new java.lang.IllegalArgumentException();

		int idC = mSAP.ancestor(iA, iB);
		
		if(idC == -1)
			return null;
		
		return mSynsetByIndex.get(idC);
	}

	// for unit testing of this class
	public static void main(String[] args)
	{
		WordNet wordnet = new WordNet(args[0], args[1]);
		StdOut.println(wordnet.isNoun("horse"));
	}
}
